package sort;

public class BucketSortLimon {
	public static long Sort(int[] list){
		long startTime = System.currentTimeMillis();

		int maxNum=0, noOfBuckets = list.length>>10;
		for(int i=0; i<list.length; i++)
			if(maxNum < list[i]) maxNum = list[i];

		int bucketSize = ++maxNum/noOfBuckets;
		int[][] arrayOfArrays = new int[++noOfBuckets+1][bucketSize<<1];

		//Adding to buckets
		for(int i=0; i<list.length; i++){
			int bucket = list[i]/bucketSize, pos = arrayOfArrays[noOfBuckets][bucket]++;
			arrayOfArrays[bucket][pos] = list[i]; 
		}
		
		for(int i=0; i<noOfBuckets; i++){
			QuickSort.IterativeSort(arrayOfArrays[i], 0, arrayOfArrays[noOfBuckets][i]-1);
		}
		
		//Putting the buckets back into list
		for(int i=0, k=0; i<noOfBuckets; i++)
			for(int j=0; j<arrayOfArrays[noOfBuckets][i]; j++) list[k++] = arrayOfArrays[i][j];
		
		return System.currentTimeMillis()-startTime;
	}
}
